package cn.good.yan.sf.t4;

import java.util.Arrays;

/**
 * 4 递归
 * 1.斐波那契数列 - 多路递归   0  1  1  2  3 5 8 13 21.。。（前一个数 + 后一个数 = 下一个值）
 * 2.斐波那契数列 - 优化
 * 3.递归过多，会出现爆栈
 * 4.从1 累加 100 的总数
 *
 * @author shengren.yan
 * @create 2024-05-13
 */
public class Demo3 {

    //  1.斐波那契数列 - 多路递归   0  1  1  2  3  5  8  13  21.。。（前一个数 + 后一个数 = 下一个值）
    public static int f1(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return f1(n - 1) + f1(n - 2);
    }

    static int[] arr = null; // 记忆法 - 缓存层

    // 2.斐波那契数列 - 优化 - 使用 记忆法
    public static int f2(int n) {
        arr = new int[n + 1];
        Arrays.fill(arr, -1);
        arr[0] = 0;
        arr[1] = 1;
        return red(n);
    }

    public static int red(int n) {
        if (arr[n] != -1) {
            return arr[n];
        }
        int num = red(n - 1) + red(n - 2);
        arr[n] = num;
        return arr[n];
    }

    // 4.从1 累加 100 的总数  ,  6 是 36
    public static int f3() {
        int sun = 0;
        int size = 8;
        for (int i = 1; i <= size; i++) {
            sun = sun + i;
        }
        System.out.println(sun);
        return sun;
    }

    public static void main(String[] args) {
        //  1.斐波那契数列 - 多路递归 , 参数是 需要加几次，从0开始，走8次的值是21
        int i1 = f1(8);
        System.out.println(i1);

        //  2.斐波那契数列 - 优化 - 使用 记忆法
        int i2 = f2(8);
        System.out.println(i2);

        // 4 从1 累加 100 的总数
        System.out.println(f3());

    }

}
